package com.jp.algorithm.priorityQueue;

import java.util.ArrayList;
import java.util.List;

public class MyPriorityQueue {
    List<Integer> list = null;
    public MyPriorityQueue(){
        list = new ArrayList<>();
    }


    public void add(int val){
        int i = list.size();
        if(i==0){
            list.add(val);
            return ;
        }
        list.add(val);
        while(i >= 0){
            if(i <  (i-1/2)){
                int tmp = list.get((i-1)/2);
                list.set((i-1)/2,val);
                list.set(i,tmp);
                i=(i-1)/2;
            }else {
                break;
            }
        }
    }

    public int take(){

        if(list.size()==0)
            return -1;

        int result = list.get(0);
        //将第一个节点值设为最后一个节点值，删除最后一个节点
        list.set(0,list.get(list.size()-1));
        list.remove(list.size()-1);

        int i = 0;
        //从第一个节点开始，依次与较小的子节点交换值
        while(i < list.size()){
            int leftIndex = i*2+1;
            int rightIndex = i*2+2;

            if(leftIndex >= list.size()){
                break;
            }
            int minIndex = leftIndex;
            if(rightIndex < list.size()){
                if(list.get(rightIndex) < list.get(leftIndex)){
                    minIndex = rightIndex;
                }
            }
            if(list.get(i) > list.get(minIndex)){
                int tmp = list.get(i);
                list.set(i,list.get(minIndex));
                list.set(minIndex,tmp);
                i = minIndex;
            }else{
                break;
            }
        }
        return result;
    }

}
